// 邻接表，表示图
// 对于有向图，有入度（in-degree）和出度（out-degree）入度是指指向该节点的边的数量，出度是指从该节点出发指向其他节点的边的数量。
// 顶点 表节点
class Vertex {
  /**
   * @description:
   * @param {*} data记录顶点节点的数值
   * @return {*}
   */
  constructor(data) {
    this.data = data; // 顶点域
    this.firstEdge = null; // 指向第一个邻接边的指针，指向当前顶点的边表中的第一个节点
    this.outNum = 0; // 在无向图中表示与顶点邻接的边的数量，在有向图中为出度
    this.inNum = 0; // 在有向图中为顶点的入度
  }
}
// 边 表节点
class Edge {
  constructor(data, weight = 0, nextEdge = null) {
    this.data = data; // 邻接点域
    this.nextEdge = nextEdge; // 指向下一条邻接边
    this.weight = weight; // 权重
  }
}

// 创建图
class Graph {
  constructor(isDirect) {
    this.eNum = 0; // 边的数目
    this.adj = []; // 顶点表
    this.isDirect = isDirect; // 是否是有向图
  }
  // 初始化顶点表
  initVertex(verArr) {
    for (let i = 0; i < verArr.length; i++) {
      let newVer = new Vertex(verArr[i]);
      this.adj[i] = newVer;
    }
  }

  // 插入新的顶点
  insertVertex(x) {
    // 创建新顶点
    let newVer = new Vertex(x);
    // 添加到当前的顶点表
    this.adj.push(newVer);
  }

  // 找到节点x在adj中所在的位置
  // 前面加上下划线表示不应该在具体实例中调用该方法
  _find(x) {
    let pos = -1;

    for (let i = 0; i < this.adj.length; i++) {
      if (x == this.adj[i].data) pos = i;
    }

    return pos;
  }

  // 判断图中是否存在边(x,y)或者<x, y>。
  //从顶点x的边表第一元素开始遍历，如果发现存在y节点则说明顶点x和顶点y之间已经有了一条边
  hasEdge(x, y) {
    let pos = this._find(x);
    if (pos > -1) {
      // 找出顶点的第一条边
      let curVer = this.adj[pos].firstEdge;

      if (!curVer) {
        // 没有与顶点x的邻接点
        return false;
      } else {
        // 至少有一个节点与顶点x是相邻的
        // 遍历顶点的所有邻接节点
        while (curVer) {
          // 如果相等，说明存在边
          if (curVer.data === y) return true;

          curVer = curVer.nextEdge;
        }

        return false;
      }
    }
  }

  // 向图中插入边(x, y)或者边<x, y>
  /**
   1.连接任意顶点，分为有向图还是无向图，
    如果是无向图的话，在插入边(x, y)后还要再插入边(y, x)，因为用邻接表来存储无向图时，顶点x的边表中具有顶点y，那么顶点y的边表中必然也有顶点x。
    如果是有向图中的话，只需要插入边<x, y>就可以
   2.在插入边的时候，首先判断下顶点x和顶点y之间是否已经存在了一条边了，只有x和y之间没有边时，才可以在顶点x和顶点y之间插入一条边
   3.在插入边的过程中，如果是有向图时，同时更新每个顶点的入度和出度，而如果是无向图的话，则分别更新了与x和y相邻的节点的数量。
   */
  addEdge(x, y, w = 0) {
    let posX = this._find(x);
    let posY = this._find(y);
    let newEdgeX = new Edge(x, w);
    let newEdgeY = new Edge(y, w);
    // 如果是无向图，在插入边(x, y)时还要插入边(y, x)
    if (!this.isDirect) {
      // <x, y>或者<y, x>边不存在
      if (!this.hasEdge(x, y) && !this.hasEdge(y, x)) {
        // 如果顶点x在顶点表中
        if (posX > -1) {
          // 取出顶点x的第一条边
          let curVer = this.adj[posX].firstEdge;
          // 如果第一条边不存在
          if (!curVer) {
            // 创建第一条边
            this.adj[posX].firstEdge = newEdgeY;
            // outNum无向图中，表示顶点邻接边的数量
            this.adj[posX].outNum++;
          } else {
            let len = this.adj[posX].outNum - 1;
            // x点的邻接边存在，往所有边之后追加边
            while (len--) {
              curVer = curVer.nextEdge;
            }
            curVer.nextEdge = newEdgeY;
            // 邻接边数量+1
            this.adj[posX].outNum++;
          }
        }
        // 如果顶点y在顶点表中
        if (posY > -1) {
          // 取出顶点y的第一条边
          let curVer = this.adj[posY].firstEdge;
          if (!curVer) {
            this.adj[posY].firstEdge = newEdgeX;
            this.adj[posY].outNum++;
          } else {
            let len = this.adj[posY].outNum - 1;
            while (len--) {
              curVer = curVer.nextEdge;
            }
            curVer.nextEdge = newEdgeX;
            this.adj[posY].outNum++;
          }
        }
        // 边的数量+1
        this.eNum++;
      }
    }
    // 有向图， 只用处理<x, y>方向的边
    else {
      if (!this.hasEdge(x, y)) {
        // 如果顶点x在顶点表中
        if (posX > -1) {
          // x顶点的第一条边
          let curVer = this.adj[posX].firstEdge;
          // 如果当前顶点没有第一个边节点
          if (!curVer) {
            this.adj[posX].firstEdge = newEdgeY;
            // x顶点的出度+1
            this.adj[posX].outNum++;
          } else {
            let len = this.adj[posX].outNum - 1;
            while (len--) {
              curVer = curVer.nextEdge;
            }
            curVer.nextEdge = newEdgeY;
            // 顶点x的出度+1
            this.adj[posX].outNum++;
          }
        }
        // 如果顶点x在顶点表中
        if (posY > -1) {
          let curVer = this.adj[posY];
          // 顶点y的入度增长
          curVer.inNum++;
        }
      }
    }
  }

  // 在图中删除边(x, y)或者边<x, y>
  // 在无向图中删除边(x, y)时，同时也需要删除(y, x)，有向图则只需要删除边<x, y>就可以
  // 由于是由邻接表表示的数据结构，当删除边(x, y)时也需要同时删除边(y, x);
  removeEdge(x, y) {
    //在图中删除边(x, y)
    if (this.hasEdge(x, y)) {
      let posX = this._find(x); //查找x顶点
      let posY = this._find(y); //查找y顶点
      let curVerX = this.adj[posX].firstEdge; // x的第一条边
      let curVerY = this.adj[posY].firstEdge; //y的第一条边
      // 首先是无向图，当删除边(x, y)时也需要同时删除边(y, x)
      if (!this.isDirect) {
        // 删除边(x, y)
        // 如果顶点的第一个节点即是要找的节点
        if (curVerX.data === y) {
          // 删除第一条边，把顶点x的nextEdge作为第一条边
          this.adj[posX].firstEdge = curVerX.nextEdge;
          this.adj[posX].outNum--;
          curVerX = null;
        }
        // curVerX如果存在，说明要找的节点不是顶点的第一个节点
        while (curVerX) {
          let preVerX = curVerX;
          // 继续查找下一条边
          curVerX = curVerX.nextEdge;
          if (curVerX && curVerX.data === y) {
            preVerX.nextEdge = curVerX.nextEdge;
            this.adj[posX].outNum--;
            curVerX = null;
          }
        }
        // 删除边(y, x)
        // 如果顶点的第一个节点即是要找的节点
        if (curVerY.data === x) {
          // 把y顶点的下一条边赋值给第一条边
          this.adj[posY].firstEdge = curVerY.nextEdge;
          this.adj[posY].outNum--;
          curVerY = null;
        }
        //curVerY如果存在，说明要找的节点不是顶点的第一个节点
        while (curVerY) {
          let preVerY = curVerY;
          curVerY = curVerY.nextEdge;
          if (curVerY && curVerY.data === x) {
            preVerY.nextEdge = curVerY.nextEdge;
            this.adj[posY].outNum--;
            curVerY = null;
          }
        }
      } else {
        // 删除边<x, y>
        // 如果顶点的第一个节点即是要找的节点
        if (curVerX.data === y) {
          this.adj[posX].firstEdge = curVerX.nextEdge;
          this.adj[posX].outNum--;
          curVerX = null;
        }
        // curVerX如果存在，说明要找的节点不是顶点的第一个节点
        while (curVerX) {
          let preVerX = curVerX;
          curVerX = curVerX.nextEdge;

          if (curVerx && curVerX.data === y) {
            preVerX.nextEdge = curVerX.nextEdge;
            this.adj[posX].outNum--;
            curVerX = null;
          }
        }
        this.adj[posY].inNum--;
      }
      this.eNum--;
    }
  }

  // 从图中删除顶点x,与删除边操作不同
  //在删除图中的一个顶点时，与此顶点所有相邻的边都要删除。
  //   两步操作，第一步删除所有以x为起点的边，第二步删除所有以x为终点的边
  deleteVertex(x) {
    let pos = this._find(x);
    if (pos > -1) {
      // 删除从x出发的边
      let curVer = this.adj[pos].firstEdge;
      while (curVer) {
        this.removeEdge(x, curVer.data);
        curVer = curVer.nextEdge;
      }
      // 删除终点是x的边
      for (let i = 0; i < this.adj.length; i++) {
        let temVer = this.adj[i].firstEdge;

        while (temVer) {
          if (temVer.data === x) {
            this.removeEdge(this.adj[i].data, temVer.data);
          }
          temVer = temVer.nextEdge;
        }
      }
      // 删除顶点x
      this.adj.splice(pos, 1);
    }
  }

  // 与顶点x邻接的所有节点
  //   不断的遍历每个顶点的边
  allNeightbors(x) {
    let pos = this._find(x);

    if (pos > -1) {
      let result = `${x}`;
      let curVer = this.adj[pos].firstEdge;

      while (curVer) {
        result += `=>${curVer.data}`;
        curVer = curVer.nextEdge;
      }

      console.log(result);
    }
  }

  // 广度优先求出图中所有的连通分量，从给定的顶点x开始
  BFSTraverse(x = this.adj[0].data) {
    // 访问过的标记数组，标记数组和顶点表 相关联的是下标
    let visited = [];
    let result = "";
    for (let i = 0; i < this.adj.length; i++) {
      visited[i] = false;
    }
    // 求以x为起始点的连通分量, 第一次A
    result = this._BFS(x, visited);
    // 如果有还未被访问过的顶点，则从该顶点继续遍历
    for (let i = 0; i < visited.length; i++) {
      if (!visited[i]) {
        let x = this.adj[i].data;
        result += `&${this._BFS(x, visited)}`; // 其他的连通分量
      }
    }
    return result;
  }

  // 实际进行广度遍历的函数，每次遍历都是 获得一个以顶点x为起点的连通分量
  _BFS(x, visited) {
    let result = "";
    let queue = [];
    let pos = this._find(x);
    if (pos > -1) {
      result += `${x}`;
      visited[pos] = true;
      // 获取到当前顶点
      let curVer = this.adj[pos];
      // 顶点x入队列
      queue.push(curVer);
      while (queue.length) {
        // 取出队列的第一个值
        curVer = queue.shift();
        // 回到顶点的表中，再次计算
        pos = this._find(curVer.data);
        curVer = this.adj[pos].firstEdge; // 第一次是 A - B
        //检测顶点的所有邻接点
        while (curVer) {
          pos = this._find(curVer.data);
          // 如果当前顶点未被访问过
          if (!visited[pos]) {
            result += `->${curVer.data}`;
            // 标记未已经访问过
            visited[pos] = true;
            queue.push(curVer);
          }
          curVer = curVer.nextEdge;
        }
      }
    }
    return result;
  }

  // 深度优先求出图中所有的连通分量，从给定的顶点x开始
  DFSTraverse(x) {
    let result = "";
    let visited = [];
    for (let i = 0; i < this.adj.length; i++) {
      visited[i] = false;
    }
    result = this._DFS(x, visited);
    // 如果还有未被访问过的顶点，则以该顶点再次出发
    for (let i = 0; i < visited.length; i++) {
      if (!visited[i]) {
        let x = this.adj[i].data;
        result += `&${this._DFS(x, visited)}`;
      }
    }
    return result;
  }

  // 实际进行深度遍历的函数，每次遍历都是得到 以顶点x为起点的连通分量
  _DFS(x, visited) {
    let result = "";
    let stack = []; // 辅助堆栈
    let pos = this._find(x);
    let curVer = this.adj[pos]; // 根据给的x值找到具体的顶点
    if (pos > -1) {
      stack.push(curVer); // 顶点x入栈
      result += `${x}`;
      // 访问过的顶点，做标记
      visited[pos] = true;
      while (stack.length) {
        // 获取栈顶元素,不能使用pop，pop会把节点删除
        curVer = stack[stack.length - 1];
        // 获取栈顶元素在顶点表中的位置
        pos = this._find(curVer.data);
        // 获取顶点的第一个邻接点
        curVer = this.adj[pos].firstEdge;
        // 邻接点存在
        while (curVer) {
          pos = this._find(curVer.data);

          if (visited[pos]) {
            // 如果该节点已经访问过了,则访问该节点的下一个相邻的节点
            curVer = curVer.nextEdge;
          } else {
            stack.push(curVer);
            result += `->${curVer.data}`;
            visited[pos] = true;
            break;
          }
        }
        // 如果顶点的所有邻接点都访问过
        if (!curVer) stack.pop();
      }
    }
    return result;
  }
}

let arr = ['V0', 'V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V7', 'V8'];
let myGraph = new Graph(0);  // 0表示无向图
myGraph.initVertex(arr);
// 插入边
myGraph.addEdge('V0', 'V1');
myGraph.addEdge('V0', 'V5');
myGraph.addEdge('V1', 'V2');
myGraph.addEdge('V1', 'V6');
myGraph.addEdge('V1', 'V8');
myGraph.addEdge('V2', 'V3');
myGraph.addEdge('V2', 'V8');
myGraph.addEdge('V3', 'V4');
myGraph.addEdge('V3', 'V6');
myGraph.addEdge('V3', 'V7');
myGraph.addEdge('V3', 'V8');
myGraph.addEdge('V4', 'V5');
myGraph.addEdge('V4', 'V7');
myGraph.addEdge('V5', 'V6');
myGraph.addEdge('V6', 'V7');
// for (let i = 0; i < arr.length; i++) {
//   myGraph.allNeightbors(arr[i]);
// }
// // 断开c和、e的连接
// myGraph.removeEdge("C", "E");
// for (let i = 0; i < arr.length; i++) {
//   myGraph.allNeightbors(arr[i]);
// }
myGraph.removeEdge('V0', 'V1');
myGraph.removeEdge('V0', 'V5');

for(let i=0; i<arr.length; i++) {
    console.log(myGraph.BFSTraverse(arr[i]));
}
// for (let i = 0; i < arr.length; i++) {
//   console.log(myGraph.DFSTraverse(arr[i]));
// }
